package com.leetcode.problems040;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/combination-sum-II/
 * @Date 2021/12/09 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {

    List<List<Integer>> list = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        combinationSum1(candidates,target,new ArrayList<>(),0);
        return list;
    }

    /**
     * 从当前下标开始，选择N个数等于target
     * @param candidates
     * @param target
     * @param res
     * @param index
     */
    public void combinationSum1(int[] candidates, int target,List<Integer> res,int index) {
        if(target == 0) {
            list.add(new ArrayList<>(res));
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            if(i > index && candidates[i] == candidates[i - 1]){
                continue;
            }
            //可以选择当前的数字
            if(candidates[i] <= target) {
                int cur = candidates[i];
                res.add(cur);
                combinationSum1(candidates,target - cur,res,i + 1);
                res.remove(res.size() - 1);
            }
        }

    }


    public static void main(String[] args) {
        int[] candidates = {10,1,2,7,6,1,5};
        int target = 8;
        System.out.println(new Solution().combinationSum2(candidates,target));;
    }
}
